/*
实验12-2 染成红黑树
分数 35
作者 陈越
单位 浙江大学

给定一系列二叉查找树，请你判断每棵树是否可以染色成为合法的红黑树。
输入格式：

输入首先在一行中给出一个正整数 k（≤10），即待处理的二叉查找树的数量，随后给出 k 棵树的信息。
每棵树首先在一行中给出正整数 n（≤30），为树中结点个数；下一行给出 n 个结点整数键值的后序遍历序列。
同行数字间以空格分隔。

输出格式：

对每棵给定的二叉查找树，如果可以将其染色成为合法的红黑树，就在一行中输出 Yes，否则输出 No。
输入样例：

3
9
1 4 5 2 8 15 14 11 7
9
1 4 5 8 7 2 15 14 11
8
6 5 8 7 11 17 15 10

输出样例：

Yes
No
Yes

*/

/*
解题思路

    红黑树的性质：

        1. 每个结点要么是红的，要么是黑的。

        2. 根结点是黑的。

        3. 每个叶结点（NIL 结点，空结点）是黑的。

        4. 如果一个结点是红的，则它的两个子结点都是黑的。

        5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

    递归判断性质：

        我们可以通过递归的方式，判断每个结点是否满足红黑树的性质。

        在递归过程中，我们需要传入一个参数：当前结点到叶结点的黑色结点数目。

        对于每个结点，我们需要判断：

            1. 根结点是黑的。

            2. 每个叶结点是黑的。

            3. 如果一个结点是红的，则它的两个子结点都是黑的。

            4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

        如果某个结点不满足上述性质，则说明该树不是红黑树。
*/

#include <iostream>
#include <vector>
using namespace std;

// typedef enum {RED, BLACK} Color;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void freeTree(TreeNode *root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

// 根据后序遍历序列构建二叉查找树
TreeNode* buildTree(vector<int>& postorder, int start, int end) {
    if (start > end) return nullptr;
    TreeNode* root = new TreeNode(postorder[end]);
    int i = start;
    while (i < end && postorder[i] < postorder[end]) i++;
    root->left = buildTree(postorder, start, i - 1);
    root->right = buildTree(postorder, i, end - 1);
    return root;
}

// 判断是否为红黑树
bool isRedBlackTree(TreeNode *root, int &blackHeight) {
    if (!root) {
        blackHeight = 1;
        return true;
    }

    int leftBlackHeight, rightBlackHeight;
    if (!isRedBlackTree(root->left, leftBlackHeight) || !isRedBlackTree(root->right, rightBlackHeight)) {
        return false;
    }

    if (leftBlackHeight != rightBlackHeight) {
        return false;
    }

    if (root->val < 0) {
        if ((root->left && root->left->val < 0) || (root->right && root->right->val < 0)) {
            return false;
        }
    }

    blackHeight = leftBlackHeight + (root->val > 0 ? 1 : 0);
    return true;
}

int main() {
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int n;
        cin >> n;
        vector<int> postorder(n);
        for (int j = 0; j < n; j++) {
            cin >> postorder[j];
        }

        TreeNode *root = buildTree(postorder, 0, n - 1);

        int blackHeight;
        if (root->val > 0 && isRedBlackTree(root, blackHeight)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }

        freeTree(root);
    }
    return 0;
}